`
https://leetcode.cn/problems/is-graph-bipartite/
`

/**
 * @param {number[][]} graph
 * @return {boolean}
 */
var isBipartite = function (graph) {
  const n = graph.length;
  // 记录图是否符合二分图性质
  let ok = true;
  // 记录图中节点的颜色，false 和 true 代表两种不同颜色
  const color = new Array(n);
  // 记录图中节点是否被访问过
  const visited = new Array(n);

  // 从 start 节点开始进行 BFS 遍历
  const bfs = (start) => {
    if (!ok) return

    const q = [];
    visited[start] = true;
    q.push(start);

    while (q.length && ok) {
      let v = q.shift();
      // 从节点 v 向所有相邻节点扩散
      for (let w of graph[v]) {
        if (!visited[w]) {
          // 相邻节点 w 没有被访问过
          // 那么应该给节点 w 涂上和节点 v 不同的颜色
          color[w] = !color[v];
          // 标记 w 节点，并放入队列
          visited[w] = true;
          q.push(w);
        } else {
          // 相邻节点 w 已经被访问过
          // 根据 v 和 w 的颜色判断是否是二分图
          if (color[w] == color[v]) {
            // 若相同，则此图不是二分图
            ok = false;
            return;
          }
        }
      }
    }
  };

  // 因为图不一定是联通的，可能存在多个子图
  // 所以要把每个节点都作为起点进行一次遍历
  // 如果发现任何一个子图不是二分图，整幅图都不算二分图
  for (let v = 0; v < n; v++) {
    if (!visited[v]) {
      // 改为使用 BFS 函数
      bfs(v);
    }
  }

  return ok;
};